package problem31_Next_Permutation;

import java.util.Arrays;

public class MySolution {
	public void nextPermutation(int[] nums) {
		int i = 0;
		for (i = nums.length - 1; i > 0; i--) {
			if (nums[i] > nums[i - 1]) {
				for(int j=nums.length-1;j>=i;j--){
					if(nums[j]>nums[i-1]){
						swap(j,i-1,nums);
						break;
					}
				}
				reverse(nums,i,nums.length-1);
				return;
			}
		}
		if (i == 0)
			Arrays.sort(nums);
	}

	private void swap(int i, int j, int[] nums) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
	
	private void reverse(int[] nums,int start,int end){
		for(int i=start;i<=(start+end)/2;i++){
			swap(i,start+end-i,nums);
		}
	}

	public static void main(String[] args) {
		int[] nums={1,3,2};
		new MySolution().nextPermutation(nums);
		System.out.println(Arrays.toString(nums));
	}
}
